package com.practice.niuke.new_direct_basics.class07;

import java.util.HashSet;

/**
 * 介绍前缀树
 * 何为前缀树? 如何生成前缀树?
 *
 * 例子:
 * 一个字符串类型的数组arr1， 另一个字符串类型的数组arr2。
 * （1）arr2中有哪些字符， 是arr1中出现的？ 请打印。
 * （2）arr2中有哪些字符， 是作为arr1中某个字符串前缀出现的？ 请打印。
 * （3）arr2中有哪些字符， 是作为arr1中某个字符串前缀出现的？ 请打印 arr2中出现次数最大的前缀。
 */
public class Code01_TrieTree {

    /**
     * 前缀树的Node
     */
    public static class TrieNode {
        // 这个节点经过了多少次
        public int pass;
        // 多少元素以这个节点结尾
        public int end;
        // 下级的路
        // HashMap<Char, Node> nexts;
        // TreeMap<Char, Node> nexts;
        public TrieNode[] nexts;

        /**
         * 若出现的所有字符都是小写字符，从'a'到'z'，
         * 如下面这样初始化这棵前缀树
         */
        public TrieNode() {
            pass = 0;
            end = 0;
            // nexts[0] == null 没有走向‘a’的路
            // nexts[0] != null 有走向‘a’的路
            // ...
            // nexts[25] != null 有走向‘z’的路
            nexts = new TrieNode[26];
        }
    }

    /**
     * 前缀树
     */
    public static class Trie {
        // 开头的空节点，pass = 0; end = 0;
        private TrieNode root;

        public Trie() {
            // 初始化开头的空节点，
            root = new TrieNode();
        }

        /**
         * 往前缀树中插入一个字符串
         * (这里以字符串数组构造前缀树为例子)
         *
         * @param word
         */
        public void insert(String word) {
            if (word == null) {
                return;
            }
            // 字符串转成字符数组
            char[] chs = word.toCharArray();
            // 从头节点开始
            TrieNode node = root;
            // 头节点的pass++
            node.pass++;
            int path = 0;
            for (int i = 0; i < chs.length; i++) { // 从左往右遍历字符
                // 走向哪条路
                path = chs[i] - 'a'; // 由字符，对应成走向哪条路
                // path处没有路就建一条路
                if (node.nexts[path] == null) {
                    node.nexts[path] = new TrieNode();
                }
                // 让node = node.nexts[path]; node.pass++;
                node = node.nexts[path];
                node.pass++;
            }
            // 最后节点的 end++
            node.end++;
        }

        /**
         * 从前缀树中删除字符串word
         * （
         * 方法：沿途每个字符（包括第一个空节点）所在节点的pass--， 最后字符所在节点的end--;
         * 注意事项：pass-- 的过程中，如果有一步 pass == 0 成立，则从当前这个节点开始后面的节点都有不要了。
         * ）
         *
         * @param word word
         */
        public void delete(String word) {
            if (search(word) != 0) { // 确定树中确实加入过word，才删除
                char[] chs = word.toCharArray();
                TrieNode node = root;
                node.pass--;
                int index = 0;
                for (int i = 0; i < chs.length; i++) {
                    index = chs[i] - 'a';
                    // pass-- 的过程中，如果有一步 pass == 0 成立
                    if (--node.nexts[index].pass == 0) {
                        // java同学如下做即可，如果是C++同学要遍历到底去析构
                        node.nexts[index] = null;
                        // ...
                        return;
                    }
                    node = node.nexts[index];
                }
                node.end--;
            }
        }

        /**
         * 从前缀树中删除字符串word(C++语言版本)
         *
         * @param word
         */
        public void deleteCPP(String word) {
            if (search(word) != 0) { // 确定树中确实加入过word，才删除
                char[] chs = word.toCharArray();
                TrieNode node = root;
                node.pass--;
                int index = 0;

                TrieNode a = null;
                int deleteIndex = -1;

                HashSet<TrieNode> deleteSet = new HashSet<>();

                for (int i = 0; i < chs.length; i++) {
                    index = chs[i] - 'a';
                    if (--node.nexts[index].pass == 0) {
                        a = a == null ? node : a;
                        deleteIndex = deleteIndex == -1 ? index : deleteIndex;

                        deleteSet.add(node.nexts[index]);
                    }
                    node = node.nexts[index];
                }
                node.end--;

                a.nexts[deleteIndex] = null;

                // deleteSet ... 析构

            }
        }

        /**
         * word这个单词之前往前缀树中加入过几次
         *
         * @param word
         * @return
         */
        public int search(String word) {
            if (word == null) {
                return 0;
            }
            char[] chs = word.toCharArray();
            TrieNode node = root;
            int index = 0;
            for (int i = 0; i < chs.length; i++) {
                index = chs[i] - 'a';
                // 提前没路了，说明这个字符串没有加入过
                if (node.nexts[index] == null) {
                    return 0;
                }
                node = node.nexts[index];
            }
            return node.end;
        }

        /**
         * 所有加入的字符串中，有几个是以pre这个字符串作为前缀的
         *
         * @param pre
         * @return
         */
        public int prefixNumber(String pre) {
            if (pre == null) {
                return 0;
            }
            char[] chs = pre.toCharArray();
            TrieNode node = root;
            int index = 0;
            for (int i = 0; i < chs.length; i++) {
                index = chs[i] - 'a';
                // 提前没路了，说明这个字符串(pre)没有加入过
                if (node.nexts[index] == null) {
                    return 0;
                }
                node = node.nexts[index];
            }
            return node.pass;
        }
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        System.out.println(trie.search("zuo"));
        trie.insert("zuo");
        System.out.println(trie.search("zuo"));
        trie.delete("zuo");
        System.out.println(trie.search("zuo"));
        trie.insert("zuo");
        trie.insert("zuo");
        trie.delete("zuo");
        System.out.println(trie.search("zuo"));
        trie.delete("zuo");
        System.out.println(trie.search("zuo"));
        trie.insert("zuoa");
        trie.insert("zuoac");
        trie.insert("zuoab");
        trie.insert("zuoad");
        trie.delete("zuoa");
        System.out.println(trie.search("zuoa"));
        System.out.println(trie.prefixNumber("zuo"));

    }

}
